/**
 * 239. 滑动窗口最大值
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function maxSlidingWindow(nums, k) {
  const stack = new Array(k);
  let top = -1;
  for (let i = 0; i < k; i += 1) {
    while (top >= 0 && nums[i] >= nums[stack[top]]) {
      top -= 1;
    }
    top += 1;
    stack[top] = i;
  }
  const result = new Array(nums.length - k + 1);
  result[0] = nums[stack[0]];
  let index = 1;
  for (let i = k; i < nums.length; i += 1) {
    if (top >= 0 && stack[0] <= i - k) {
      stack.shift();
      stack.push();
      top -= 1;
    }
    while (top >= 0 && nums[i] >= nums[stack[top]]) {
      top -= 1;
    }
    top += 1;
    stack[top] = i;
    result[index] = nums[stack[0]];
    index += 1;
  }
  return result;
}

console.log(displayBaseArray(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)) === '[3,3,5,5,6,7]');
console.log(displayBaseArray(maxSlidingWindow([1], 1)) === '[1]');
console.log(displayBaseArray(maxSlidingWindow([5, 3, 4], 1)) === '[5,3,4]');
console.log(displayBaseArray(maxSlidingWindow([7, 2, 4], 2)) === '[7,4]');
